package ev.traffic;

import ev.agent.*;
import ev.space.*;

import java.util.ArrayList;
import swarm.collections.List;
import swarm.collections.ListIndex;
import swarm.Globals;
public class Dijkstra{
	static ArrayList<Side> map = null;
    static ArrayList<Integer> redAgg = null;
    static ArrayList<Integer> blueAgg = null;
    static Side[] parents = null;
	static ArrayList<Integer> roadLine = null;
	//a method just for planning the roadMap
	public static void getPath(int startPoint,int endPoint,List subList){
        // set the road node;
		int length = CitySpace.nodeMap.size();
        int[] nodes = new int[length];
        for(int i =0;i < length;i++)
        	nodes[i] = i;
        // initilize the citymap
        map = CitySpace.roadMap; 

        //set the redAgg,and put the startPoint in it 
		redAgg = new ArrayList<Integer>();
        redAgg.add(startPoint);

        // put the rest of nodes  int the blueAgg
        blueAgg = new ArrayList<Integer>();
        for (int i = 0; i < nodes.length; i++){
            if(nodes[i] == startPoint)
				continue;
			blueAgg.add(nodes[i]);
		}

        // initilize the parents,tell the sys all the connect-conditions between the nodes and the 
		// startPoint
        parents = new Side[nodes.length];
        parents[0] = new Side(-1, startPoint, 0);
        for (int i = 0; i < blueAgg.size(); i++) {
            int n = blueAgg.get(i);
            parents[i + 1] = new Side(startPoint, n, getWeight(startPoint, n));
        }
        while (blueAgg.size() > 0) {
            MinShortPath msp = getMinSideNode();
			int start = msp.getFirstNode();
            int node = msp.getLastNode();
			//roadline is the the way how the car goes,so here we just need to know the 
			//way btw the startPoint and the endPoint,that's enough :)
			if((startPoint == start)&&(node == endPoint)){
					roadLine = msp.getNodeList();
					return;
			}
            redAgg.add(node); 
            setWeight(node);

			ArrayList<Nodes> nodeMap = CitySpace.nodeMap;
			for(int i = 0;i < nodeMap.size();i++){					
					Nodes tempnodes = nodeMap.get(i);
			  		if(node == tempnodes.getNum()){
						if(tempnodes.getSub() != null){
							Substation substation = tempnodes.getSub();
							substation.setDistance(msp.getWeight());
						}
					}
			}
        }
    }
    public static void sort(int startPoint,List subList) {
		//here nodes should be subNum
		int length = CitySpace.nodeMap.size();
        int[] nodes = new int[length];
        for(int i =0;i < length;i++)
        	nodes[i] = i;
        map = CitySpace.roadMap;

        redAgg = new ArrayList<Integer>();
        redAgg.add(startPoint);

        blueAgg = new ArrayList<Integer>();
        for (int i = 0; i < nodes.length; i++){
            if(nodes[i] == startPoint)
				continue;
			blueAgg.add(nodes[i]);
		}

        parents = new Side[nodes.length];
        parents[0] = new Side(-1, startPoint, 0);
        for (int i = 0; i < blueAgg.size(); i++) {
            int n = blueAgg.get(i);
            parents[i + 1] = new Side(startPoint, n, getWeight(startPoint, n));
        }
        while (blueAgg.size() > 0) {
            MinShortPath msp = getMinSideNode();
            //if(msp.getWeight() == -1)
              //  msp.outputPath(startPoint);
            //else
              //  msp.outputPath();
			//according to the program,we just set the distance of
			//every substation :)
          
            int node = msp.getLastNode();
			int weight = msp.getWeight();
            redAgg.add(node);             
			ArrayList<Nodes> nodeMap = CitySpace.nodeMap;
			for(int i = 0;i < nodeMap.size();i++){					
					Nodes tempnodes = nodeMap.get(i);
			  		if(node == tempnodes.getNum()){
						if(tempnodes.getSub() != null){
							Substation substation = tempnodes.getSub();	
							substation.setDistance(weight);
						}
					}
            setWeight(node);
        }
			}
    }
    /** *//**
     * @param parents
     * @param node
     * @return
     */
    public static int getParent(Side[] parents, int node) {
        if (parents != null) {
            for (Side nd : parents) {
                if (nd.getNode() == node){
                    return nd.getPreNode();
                }
            }
        }
        return -1;
    }

    /** *//**
     * @param preNode
     * @param map
     * @param blueAgg
     */
    public static void setWeight(int preNode) {
        if (map != null && parents != null && blueAgg != null){
            for (int node : blueAgg) {
                MinShortPath msp=getMinPath(node);
                int w1 = msp.getWeight();
                if (w1 == -1)
                    continue;
                for (Side n : parents) {
                    if (n.getNode() == node) {
                        if (n.getWeight() == -1 || n.getWeight() > w1) {
                            n.setWeight(w1);
                            n.setPreNode(preNode);
                            break;
                        }
                    }
                }
            }
        }
    }
    /** *//**
     * 
     * @param map
     * @param preNode
     * @param node
     * @return
     */
    public static int getWeight(int preNode, int node) {
        if (map != null) {
            for (Side s : map) {
                if (s.getPreNode() == preNode && s.getNode() == node)
                    return s.getWeight();
            }
        }
        return -1;
    }
    /** *//**
     * 
     * @param map
     * @param blueAgg
     * @return
     */
    public static MinShortPath getMinSideNode() {
        MinShortPath minMsp = null;
        if (blueAgg.size() > 0) {
            int index = 0;
            for (int j = 0; j < blueAgg.size(); j++) {
                MinShortPath msp = getMinPath(blueAgg.get(j));
                if (minMsp == null || msp.getWeight()!=-1 &&  msp.getWeight() < minMsp.getWeight()) {
                    minMsp = msp;
                    index = j;
                }
				if(minMsp.getWeight() == -1)
						minMsp = null;
            }
            blueAgg.remove(index);
        }
        return minMsp;
    }
    /** *//**
     * @param node
     * @return
     */
    public static MinShortPath getMinPath(int node) {
        MinShortPath msp = new MinShortPath(node);
        if (parents != null && redAgg != null) {
            for (int i = 0; i < redAgg.size(); i++) {
                MinShortPath tempMsp = new MinShortPath(node);
                int parent = redAgg.get(i);
                int curNode = node;
				while (parent > -1) {
                    int weight = getWeight(parent, curNode);
                    if (weight > -1) {
                        tempMsp.addNode(parent);
                        tempMsp.addWeight(weight);
                        curNode = parent;
                       	parent = getParent(parents, parent);
                    } else
                        break;
                }
                if (msp.getWeight() == -1 || tempMsp.getWeight()!=-1 && msp.getWeight() > tempMsp.getWeight())
                    msp = tempMsp;
            }
        }
        return msp;
    }
}

/** *//**
 * 
 */
class MinShortPath {
    private ArrayList<Integer> nodeList;
    private int weight;
	public MinShortPath(int node) {
        nodeList = new ArrayList<Integer>();
        nodeList.add(node);
        weight = -1;
    }
    public ArrayList<Integer> getNodeList() {
        return nodeList;
    }

    public void setNodeList(ArrayList<Integer> nodeList) {
        this.nodeList = nodeList;
    }

    public void addNode(int node) {
        if (nodeList == null)
            nodeList = new ArrayList<Integer>();
        nodeList.add(0, node);
    }
    public int getLastNode() { 
        int size = nodeList.size();
        return nodeList.get(size - 1);
    }

	public int getFirstNode(){
		return nodeList.get(0);
	}

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public void outputPath() {
        outputPath(-1);
 }

    public void outputPath(int srcNode) {
        String result = "[";
        if (srcNode != -1)
            nodeList.add(srcNode);

        for (int i = 0; i < nodeList.size(); i++) {
            result += "" + nodeList.get(i);
            if (i < nodeList.size() - 1)
                result += ",";
        }
        result += "]:" + weight;
        System.out.println(result);
    }

    public void addWeight(int w) {
        if (weight == -1)
            weight = w;
        else
            weight += w;
    }
}

